Users are increasingly relying upon cloud-based resources for online activities such as conducting business and personal communications, online meetings, screen-sharing, video chats, messaging, and otherwise using various resources available from service providers. Various application and user data associated with user interactions may be maintained in databases associated with the resources. Generally, a database may include many different individual partitions or database nodes to which data is allocated. The partitions may be spread across multiple different physical devices and servers. Data entries may be associated with identifiers such as key values that indicate which of the partitions corresponds to the data. The identifiers may be used to allocate and reference the data to perform operations such as adding, accessing, and modifying corresponding data entries.
Over time, the amount of data stored in a database grows and at some point the storage capacity may be expanded to accommodate the volume of data and requests. One traditional database expansion approach involves stopping services for and/or access to the database, adding new storage/partitions to the database, and then reallocating all of the pre-existing data across the new arrangement of partitions. In this approach, pre-existing data is moved to new locations and this moving process may be quite time consuming for large scale databases. As such, traditional database expansion techniques may be quite disruptive to services provided to users and take a considerable amount of time to process and re-insert data at new locations in the updated arrangement of partitions.